#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

// 定义多项式结点结构体（带表头结点）
typedef struct Node {
    double coef;   // 系数（使用double因为测试文件中含有小数）（不用float因为测试文件中有指数过高如11次方，float精度不够）
    int expn;      // 指数（测试文件中的指数都是整数所以使用int）
    struct Node* next; // 指向下一个结点的指针
} PolyNode, *Polynomial; // PolyNode为结构体类型别名，Polynomial为结构体指针类型别名

// 函数声明（所有函数均使用多项式头结点操作链表）
void createPolyn(Polynomial* P);          // 读取函数（从用户输入的文件路径读取多项式并初始化链表）
void insertNode(Polynomial P, double coef, int expn); // 排序函数（   按指数降序插入结点，自动合并同类项）
void destroyPolyn(Polynomial P);          // 清理函数（销毁多项式，释放所有数据结点，保留头结点）
void printPolyn(Polynomial P);            // 输出函数（以类数学表达式格式输出多项式（如：3x^2-2x+5））
void addPolyn(Polynomial A, Polynomial B, Polynomial* C); // 加法函数（计算A+B，结果存入C）
void subPolyn(Polynomial A, Polynomial B, Polynomial* C); // 减法函数（计算A-B，结果存入C）
void mulPolyn(Polynomial A, Polynomial B, Polynomial* C); // 乘法函数（计算A*B，结果存入C）
double calculateValue(Polynomial P, int x); // 计算多项式在x处的值（double用于小数系数）
void derivativePolyn(Polynomial A, Polynomial* B); // 求导函数（计算A的导函数，结果存入B）

// 显示操作菜单（用户交互界面）
void menu() {
    printf("===== 一元稀疏多项式计算器 =====\n");
    printf("1. 从文件读取多项式A和B\n");
    printf("2. 显示当前多项式A和B\n");
    printf("3. 计算A+B\n");
    printf("4. 计算A-B\n");
    printf("5. 计算A*B\n");
    printf("6. 计算多项式在x处的值\n");
    printf("7. 求多项式的导函数\n");
    printf("8. 退出计算器\n");
}



// 从用户输入的文件路径读取多项式
void createPolyn(Polynomial* P) {
    char path[256];       // 存储用户输入的文件路径（最大255字符）
    int n;                // 多项式的项数（文件第一个数字）
    double coef;          // 系数
    int expn;             // 指数
    char comma;           // 用于检查逗号分隔符（确保文件格式正确）

    printf("请输入文件路径(如:C:\\Test_Data_1A.txt): ");
    scanf("%s", path);    // 读取用户输入的文件路径

    FILE* fp = fopen(path, "r"); // 以只读模式打开文件
    if (!fp) { // 文件打开失败时
        printf("错误：无法打开文件 %s\n", path);
        return;
    }

    // 读取项数n（第一个数字），并检查是否有逗号分隔符
    // fscanf返回成功读取的参数个数，此处需要读取n和逗号两个参数
    if (fscanf(fp, "%d%c", &n, &comma) != 2 || comma != ',') {
        printf("错误：文件格式无效（未找到项数或分隔符）\n");
        fclose(fp); // 关闭文件
        return;
    }

    // 清空当前多项式（避免旧数据残留）
    (*P)->next = NULL;

    // 读取n个项（每个项包含系数和指数）
    for (int i = 0; i < n; i++) {
        // 前n-1项需要检查逗号分隔符，最后一项不需要
        if (i < n-1) {
            // 格式示例：coef1,exp1, （注意末尾逗号，一共是三个）
            if (fscanf(fp, "%lf,%d%c", &coef, &expn, &comma) != 3 || comma != ',') {
                printf("错误：文件格式错误（第%d项)\n", i+1);
                fclose(fp);
                return;
            }
        } else {
            // 最后一项格式示例：coefn,expn（无末尾逗号，一共是两个）
            if (fscanf(fp, "%lf,%d", &coef, &expn) != 2) {
                printf("错误：文件格式错误（第%d项)\n", i+1);
                fclose(fp);
                return;
            }
        }
        // 插入当前项到多项式链表中（自动排序并合并同类项）
        insertNode(*P, coef, expn);
    }

    // 检查文件正确性
    if (fgetc(fp) != EOF) {//在读完文件中预期的内容后（比如代码中已经按格式读取了多项式的项数和所有项），尝试读取下一个字符：如果 fgetc(fp) 返回 EOF，说明文件刚好读完，没有多余内容。如果 fgetc(fp) 返回 非 EOF 的值（比如空格、换行、多余的数字 / 符号等），说明文件里还有未被处理的多余内容，于是打印警告
        printf("警告：文件包含多余内容\n");
    }

    fclose(fp); // 关闭文件
    printf("成功从文件 %s 读取多项式(共%d项)\n", path, n);
}

// 按指数降序插入结点，并且合并同类项
void insertNode(Polynomial P, double coef, int expn) {
    if (fabs(coef) < 1e-6) return; // 系数接近0时不插入（浮点精度问题，避免误差）

    PolyNode* prev = P;       // 前驱结点指针（初始指向头结点）
    PolyNode* curr = P->next; // 当前结点指针（初始指向第一个数据结点）
    // 寻找插入位置：找到第一个指数≤当前项指数的结点（保持链表降序）
// 当当前结点不为空，并且当前结点的指数大于要插入项的指数时，继续循环，目的是找到合适的插入位置，以保证链表按指数降序排列。
    while (curr && curr->expn > expn) {
        prev = curr;      // 前驱结点后移
        curr = curr->next; // 当前结点后移
    }

    // 情况1：当前结点存在且指数相同（合并同类项）
    if (curr && curr->expn == expn) {
        curr->coef = curr->coef + coef; // 系数相加
        // 合并后系数接近0时，删除该结点（避免存储无意义项）
        if (fabs(curr->coef) < 1e-6) {
            prev->next = curr->next; // 前驱结点跳过当前结点
            free(curr);              // 释放当前结点内存
        }
        return; // 合并完成，无需插入新结点
    }

    // 情况2：当前结点不存在或指数不同（插入新结点）
    PolyNode* newNode = (PolyNode*)malloc(sizeof(PolyNode)); // 分配新结点内存
    newNode->coef = coef;  // 设置新结点系数
    newNode->expn = expn;  // 设置新结点指数
    newNode->next = curr;  // 新结点的next指向当前结点
    prev->next = newNode;  // 前驱结点的next指向新结点（完成插入）
}

// 销毁多项式（释放所有数据结点，保留头结点以便后续重用）
void destroyPolyn(Polynomial P) {
    PolyNode* p = P->next; // 从第一个数据结点开始释放
    while (p) {            // 遍历所有数据结点
        PolyNode* temp = p; // 临时保存当前结点
        p = p->next;        // 指针后移
        free(temp);         // 释放当前结点内存
    }
    P->next = NULL; // 头结点的next置空（避免野指针）
}

// 以类数学表达式格式输出多项式（如：-3.1x^11+5x^8+2x+7）
void printPolyn(Polynomial P) {
    PolyNode* p = P->next; // 指向第一个数据结点
    if (!p) {              // 无数据结点（空多项式）
        printf("0\n");
        return;
    }

    int first = 1; // 标记是否为第一个项（控制符号输出）
    while (p) {
        double coef = p->coef; // 当前项的系数
        int expn = p->expn;    // 当前项的指数

        // 处理符号（第一个项和后续项的符号规则不同）
        if (first) {
            if (coef < 0) {
                printf("-"); // 第一个项为负，直接输出负号
            }
        } else {
            if (coef > 0) {
                printf("+"); // 后续正项输出加号
            } else {
                printf("-"); // 后续负项输出减号（系数已取绝对值）
            }
        }

        // 处理系数（取绝对值，因为符号已单独处理）
        double absCoef = fabs(coef);
        if (expn != 0) { // 非常数项（x的指数≥1）
            if (absCoef != 1.0) { // 系数绝对值≠1时输出系数（如2x、-3x^2）
                printf("%g", absCoef);
            } // 系数绝对值=1时不输出系数（如x、-x^3）
        } else { // 常数项（x^0），必须输出系数（如5、-3）
            printf("%g", absCoef);
        }

        // 处理x和指数（仅当指数>0时显示x）
        if (expn > 0) {
            printf("x");          // 显示x
            if (expn != 1) {      // 指数≠1时显示指数（如x^3）
                printf("^%d", expn);
            } // 指数=1时省略^1（如x）
        }

        first = 0;  // 标记第一个项已处理
        p = p->next; // 指针后移
    }
    printf("\n"); // 换行结束输出
}

// 多项式加法：C = A + B
// 参数说明：A、B是待加的多项式，*C是结果多项式的头结点指针地址
void addPolyn(Polynomial A, Polynomial B, Polynomial* C) {
    *C = (PolyNode*)malloc(sizeof(PolyNode)); // 初始化结果多项式头结点
    (*C)->next = NULL;

    PolyNode* a = A->next; // 指向A的第一个数据结点
    PolyNode* b = B->next; // 指向B的第一个数据结点

    // 遍历A和B的所有结点，逐项相加
    while (a || b) {
        double coef; // 当前项的系数（相加后的值）
        int expn;    // 当前项的指数（取较大的或相同的）

        // 情况1：B已遍历完 或 A的当前项指数更大（取A的项）
        if (!b || (a && a->expn > b->expn)) {
            coef = a->coef;
            expn = a->expn;
            a = a->next; // A指针后移
        }
        // 情况2：A已遍历完 或 B的当前项指数更大（取B的项）
        else if (!a || (b && b->expn > a->expn)) {
            coef = b->coef;
            expn = b->expn;
            b = b->next; // B指针后移
        }
        // 情况3：指数相同（系数相加）
        else {
            coef = a->coef + b->coef; // 系数相加
            expn = a->expn;           // 指数相同
            a = a->next;              // A和B指针都后移
            b = b->next;
        }

        // 将当前项插入结果多项式（自动处理系数为0的情况）
        insertNode(*C, coef, expn);
    }
}

// 多项式减法：C = A - B（等价于A + (-B)）
// 参数说明：A、B是待减的多项式，*C是结果多项式的头结点指针地址
void subPolyn(Polynomial A, Polynomial B, Polynomial* C) {
    *C = (PolyNode*)malloc(sizeof(PolyNode)); // 初始化结果多项式头结点
    (*C)->next = NULL;

    PolyNode* a = A->next; // 指向A的第一个数据结点
    PolyNode* b = B->next; // 指向B的第一个数据结点

    // 遍历A和B的所有结点，逐项相减
    while (a || b) {
        double coef; // 当前项的系数（相减后的值）
        int expn;    // 当前项的指数（取较大的或相同的）

        // 情况1：B已遍历完 或 A的当前项指数更大（取A的项）
        if (!b || (a && a->expn > b->expn)) {
            coef = a->coef;
            expn = a->expn;
            a = a->next; // A指针后移
        }
        // 情况2：A已遍历完 或 B的当前项指数更大（取B的项的相反数）
        else if (!a || (b && b->expn > a->expn)) {
            coef = -b->coef; // B的系数取反（实现减法）
            expn = b->expn;
            b = b->next; // B指针后移
        }
        // 情况3：指数相同（系数相减）
        else {
            coef = a->coef - b->coef; // 系数相减
            expn = a->expn;           // 指数相同
            a = a->next;              // A和B指针都后移
            b = b->next;
        }

        // 将当前项插入结果多项式（自动处理系数为0的情况）
        insertNode(*C, coef, expn);
    }
}

// 多项式乘法：C = A * B（逐项相乘后合并同类项）
// 参数说明：A、B是待乘的多项式，*C是结果多项式的头结点指针地址
void mulPolyn(Polynomial A, Polynomial B, Polynomial* C) {
    *C = (PolyNode*)malloc(sizeof(PolyNode)); // 初始化结果多项式头结点
    (*C)->next = NULL;
    double coef; // 当前项的系数（相乘后的值）
    int expn;    // 当前项的指数（相加后的值）
    PolyNode* a = A->next; // 指向A的第一个数据结点
    while (a) {            // 遍历A的每一个项
        PolyNode* b = B->next; // 指向B的第一个数据结点
        while (b) {        // 遍历B的每一个项
            coef = a->coef * b->coef; // 系数相乘（double类型）
            expn = a->expn + b->expn;    // 指数相加（整数）
            insertNode(*C, coef, expn);      // 插入结果多项式（自动合并同类项）
            b = b->next; // B指针后移
        }
        a = a->next; // A指针后移
    }
}

// 计算多项式在x处的值（支持小数系数）
// 参数说明：P是多项式头结点，x是变量值（整数）
// 返回值：多项式在x处的值（double类型）
double calculateValue(Polynomial P, int x) {
    double result = 0.0;    // 计算结果初始化为0
    PolyNode* p = P->next;  // 指向第一个数据结点
    while (p) {             // 遍历所有项
        // 计算当前项的值：coef * x^expn（使用math.h的pow函数计算幂）
        result += p->coef * pow(x, p->expn);
        p = p->next;        // 指针后移
    }
    return result;
}

// 求多项式的导函数（逐项求导：coef*expn, expn-1；常数项导数为0）
// 参数说明：A是原多项式，*B是导函数的头结点指针地址
void derivativePolyn(Polynomial A, Polynomial* B) {
    *B = (PolyNode*)malloc(sizeof(PolyNode)); // 初始化导函数头结点
    (*B)->next = NULL;

    PolyNode* a = A->next; // 指向原多项式的第一个数据结点
    while (a) {            // 遍历原多项式的所有项
        if (a->expn == 0) { // 常数项（指数为0）导数为0，跳过
            a = a->next;
            continue;
        }
        // 计算导数的系数和指数：d/dx (coef*x^expn) = coef*expn * x^(expn-1)
        double coef = a->coef * a->expn; // 导数的系数
        int expn = a->expn - 1;          // 导数的指数
        insertNode(*B, coef, expn);      // 插入导函数多项式
        a = a->next; // 指针后移
    }
}

int main() {
    Polynomial A = (PolyNode*)malloc(sizeof(PolyNode)); // 初始化多项式A的头结点
    Polynomial B = (PolyNode*)malloc(sizeof(PolyNode)); // 初始化多项式B的头结点
    A->next = NULL; // 头结点A初始无后续结点
    B->next = NULL; // 头结点B初始无后续结点
    Polynomial result = NULL; // 用于存储运算结果的临时多项式

    int choice; // 用户输入的操作选项
    int x;      // 计算多项式值时的变量x

    menu();

    // 主循环：持续接收用户操作直到选择退出（输入8）
    while (1) {
        printf("\n请输入操作选项(1-8): ");
        scanf("%d", &choice); // 读取用户输入的选项

        switch (choice) {
            case 1: {
                // 从文件读取多项式A和B
                printf("=== 读取多项式A ===\n");
                createPolyn(&A); // 传入A的头结点指针地址，修改其链表内容
                printf("\n=== 读取多项式B ===\n");
                createPolyn(&B);
                break;
            }
            case 2: {
                // 显示当前多项式A和B
                printf("多项式A: "); printPolyn(A);
                printf("多项式B: "); printPolyn(B);
                break;
            }
            case 3: {
                // 计算A+B并输出结果
                addPolyn(A, B, &result); // 计算A+B，结果存入result
                printf("A+B结果: "); printPolyn(result);
                destroyPolyn(result); // 释放结果链表内存（仅保留头结点）
                break;
            }
            case 4: {
                // 计算A-B并输出结果
                subPolyn(A, B, &result);
                printf("A-B结果: "); printPolyn(result);
                destroyPolyn(result);
                break;
            }
            case 5: {
                // 计算A*B并输出结果
                mulPolyn(A, B, &result);
                printf("A*B结果: "); printPolyn(result);
                destroyPolyn(result);
                break;
            }
            case 6: {
                // 计算多项式在x处的值
                printf("请输入x的值: ");
                scanf("%d", &x);
                // 分别计算A和B在x处的值并输出（%g格式自动省略无意义小数位）
                printf("多项式A在x=%d处的值: %g\n", x, calculateValue(A, x));
                printf("多项式B在x=%d处的值: %g\n", x, calculateValue(B, x));
                break;
            }
            case 7: {
                // 计算并输出A和B的导函数
                Polynomial derivA = (PolyNode*)malloc(sizeof(PolyNode)); // 导函数A的头结点
                derivA->next = NULL;
                derivativePolyn(A, &derivA); // 计算A的导函数，结果存入derivA
                printf("A的导函数为: "); printPolyn(derivA);
                destroyPolyn(derivA); // 释放导函数A的内存

                Polynomial derivB = (PolyNode*)malloc(sizeof(PolyNode)); // 导函数B的头结点
                derivB->next = NULL;
                derivativePolyn(B, &derivB); // 计算B的导函数，结果存入derivB
                printf("B的导函数为: "); printPolyn(derivB);
                destroyPolyn(derivB); // 释放导函数B的内存
                break;
            }
            case 8: {
                // 退出程序前释放所有内存
                printf("退出计算器\n");
                destroyPolyn(A); // 释放A的所有数据结点（保留头结点）
                destroyPolyn(B); // 释放B的所有数据结点（保留头结点）
                free(A);         // 释放A的头结点
                free(B);         // 释放B的头结点
                return 0;
            }
            default: printf("输入错误，请重新输入！\n"); // 处理非法输入
        }
    }
}
